package com.tgy.dynamic.programming;

/**
 * @Author: tgy
 * @Date: 2020/11/11 9:15 下午
 * LIS : longest increasing subsequence
 */
public class LIS {

    /**
     * 获取最长升序序列
     * @param array 查找的数组
     * @return 最长的长度
     */
    public int lis(int[] array) {

        int[] dp = new int[array.length];

        dp[0] = 1;
        int inMax = 1,outMax = inMax;
        for (int i = 1; i < array.length; i++) {

            inMax = 1;
            for (int j = i - 1; j >= 0; j--) {

                if (array[j] < array[i] && inMax < dp[j] + 1) {
                    inMax = dp[j] + 1;
                }
            }

            dp[i] = inMax;

            if (inMax > outMax) {

                outMax = inMax;
            }

        }

        return outMax;
    }
}
